package com.ma.dp.a01;

/**
 * @ClassName Solution312
 * @Author: mayongqiang
 * @DATE 2022/4/16 15:27
 * @Description: 戳气球
 */
/*  有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组nums中。
    现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。
        这里的 i - 1 和 i + 1 代表和i相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
    求所能获得硬币的最大数量。*/
public class Solution312 {

    public static void main(String[] args) {
        /*输入：nums = [3,1,5,8]
        输出：167
        解释：
        nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
        coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167*/
        System.out.println(maxCoins(new int[]{3, 1, 5, 8}));
    }

    public static int maxCoins(int[] nums) {
        /*
         0、加上边界条件
                新定义数组 其中 point[1...n+2] = [1,nums[0],..nums[n-1],1]
         1、定义dp数组的含义
                dp[i][j] = x 代表 戳破气球i到气球j之间的所有气球，可以获得的最高分数为x
                               要求的答案即为 dp[0][n+1]
         2、base case
                即为 j<=i+1 dp[i][j] = 0
         3、状态转移
                寻找子状态  dp[i][j] (i,j)内所有气球都被戳破的上一个状态是还有一个未被戳破
                    假设最后一个戳破的气球为k  dp[i][j] = dp[i][k]+dp[k][j] + point[i]*point[k]*point[j]
         4、穷举状态的顺序问题
                 应该先得到子状态 dp[i][j] 需要 dp[i][i+1..j-1] dp[i+1..j-1][j]
                 需要 dp[i][j-1],dp[i][j-2]...dp[i][i+1]  j从左向右遍历
                 需要 dp[i+1][j],dp[i+2][j]...dp[j-1][j]  i从下往上
        */

        int n = nums.length;
        int[] point = new int[n + 2];
        point[0] = point[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            point[i] = nums[i - 1];
        }
        int[][] dp = new int[n + 2][n + 2];
        for (int i = n; i >= 0; i--) {
            for (int j = i + 1; j < n + 2; j++) {
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j],
                            dp[i][k] + dp[k][j] + point[i] * point[k] * point[j]);
                }
            }
        }
        return dp[0][n + 1];
    }
}
